package com.cn.algorithm02.class07;

import java.util.Arrays;
import java.util.PriorityQueue;

/***
 * @author: hels
 * @description: 线段重合问题，有许多线段，记录起点和终点都是整数且是闭区间，
 * 返回这些重合线段最多的区域包含几个线段（线段重合区域长度>=1)
 **/
public class C11_LineCoinCide {
    public static class Line implements Comparable<Line> {
        public int start;
        public int end;

        public Line(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(Line o) {
            return start - o.start;
        }
    }

    public static void main(String[] args) {
        Line line1 = new Line(1, 10 );
        Line line2 = new Line(3, 5);
        Line line3 = new Line(2, 5);
        Line line4 = new Line(4, 10);
        Line line5 = new Line(7, 10);
        Line line6 = new Line(7, 10);
        Line line7 = new Line(7, 10);
        Line[] lines = {line1, line2, line3, line4, line5/*, line6, line7*/};
        Arrays.sort(lines);
        System.out.println(CoinCide1(lines));
        System.out.println(CoinCide2(lines));

    }

    // 方法二 小根堆方式
    /*
    1 创建一个小根堆用于存放线段终点值
    2 依次将线段的起点与小根堆比较，小于的弹出，并记录弹出后的heapsize
    3 将heapsize与ans取最大值返回
    注意：由于小根堆存储的终点值依次要与起点比较，因此线段数组要按照起点大小顺序便利，否则会出现问题。
    * */
    public static int CoinCide2(Line[] lines) {
        if (lines == null || lines.length == 0) return 0;
        int ans = 0;
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>();

        for (Line l : lines) {
            while (!heap.isEmpty() && heap.peek() <= l.start) {
                heap.poll();
            }
            heap.offer(l.end);
            ans = Math.max(ans, heap.size());
        }

        return ans;
    }

    // 方法一（对数器），暴力破解法
    // 找到线段最小起点、最大终点，例如minStart=1,maxEnd=100，将整个区域单位长度的范围依次和线段比较记录重合的最大值
    public static int CoinCide1(Line[] lines) {
        if (lines == null || lines.length == 0) return 0;
        int ans = 0;
        int minStart = lines[0].start, maxEnd = lines[0].end;
        // 1 找到最小和最大值
        for (int i = 1; i < lines.length; i++) {
            minStart = minStart < lines[i].start ? minStart : lines[i].start;
            maxEnd = maxEnd > lines[i].end ? maxEnd : lines[i].end;
        }

        // 暴力破解
        for (double i = minStart + 0.5; i < maxEnd; i++) {
            int value = 0;
            for (int j = 0; j < lines.length; j++) {
                value = lines[j].start < i && lines[j].end > i ? value + 1 : value;
            }
            ans = Math.max(ans, value);
        }

        return ans;
    }
}

